package Array;

/**
 * 135. 分发糖果
 * n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
 * 你需要按照以下要求，给这些孩子分发糖果:
 * 每个孩子至少分配到 1 个糖果。
 * 相邻两个孩子评分更高的孩子会获得更多的糖果。
 * 请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

 思路： 根据这两个条件,先定义一个数组count[]，用于存储每个孩子需要的糖果数,
      因为相邻的孩子评分最高的获取糖果最多，所以我们可以使用贪心思想，
      先从左到右遍历数组，确保每个孩子都比他左边评分低的孩子获取更多的糖果，
      然后再从右到左遍历数组，确保每个孩子都比他右边评分低的孩子获取更多的糖果。    这就是贪心思想的实现， 求除自身项外数组中其余元素的乘积，也可以用到贪心思想
    思路概况：对于贪心思路的使用，考虑到当前元素的左右边界条件，如果左右边规则的判断统一，那么就可以使用贪心思想。
 解题步骤：
    1： 初始化： 定义一个数组count[]，用于存储每个孩子需要的糖果数，初始化每个孩子都至少分配到1个糖果。
    2： 从左到右遍历数组： 遍历数组，如果当前孩子的评分比前一个孩子高，则当前孩子需要比前一个孩子多1个糖果。
    3： 从右到左遍历数组： 遍历数组，如果当前孩子的评分比后一个孩子高，则当前孩子需要比后一个孩子多1个糖果。 但是注意：这里我们要取当前孩子糖果数和从右边计算出来的糖果数的最大值，这是因为当前孩子的糖果数可能在左向右遍历时已经被增加过了。
    4： 计算结果： 遍历count数组，并累加返回
 */
public class CandyQuestion {

    public int candy(int[] ratings) {
        if(ratings == null){
            return -1;
        }
        if(ratings.length <2){
            return ratings.length;
        }
        // 1: 定义计数数组并初始化
        int[] count = new int[ratings.length];
        for (int i = 0; i < count.length; i++) {
            count[i] = 1;
        }
        // 2:从左到右遍历数组,如果当前孩子的评分比前一个孩子高，则当前孩子需要比前一个孩子多1个糖果
        for (int i = 1; i <ratings.length ; i++) {
            if(ratings[i] > ratings[i-1]){
                count[i] = count[i-1] + 1;
            }
        }
        // 3: 从右到左遍历数组，如果当前孩子的评分比后一个孩子高，则当前孩子需要比后一个孩子多1个糖果，但是要取当前孩子糖果数和从右边计算出来的糖果数的最大值
        for (int i = ratings.length -2 ; i >=0 ; i--) {
            if(ratings[i] > ratings[i+1]){
                count[i] = Math.max(count[i+1]+1,count[i]);
            }
        }
        //4: 计算返回值
        int sum = 0;
        for (int i = 0; i < count.length; i++) {
            sum += count[i];
        }
        return sum;
    }
}
